/* ************************************************************************** */
/*                                                                            */
/*                                                        :::      ::::::::   */
/*   HashTable.h                                        :+:      :+:    :+:   */
/*                                                    +:+ +:+         +:+     */
/*   By: TYTY000 <767280080@qq.com>                 +#+  +:+       +#+        */
/*                                                +#+#+#+#+#+   +#+           */
/*   Created: 2024/04/23 21:23:08 by TYTY000           #+#    #+#             */
/*   Updated: 2024/04/23 21:29:35 by TYTY000          ###   ########.fr       */
/*                                                                            */
/* ************************************************************************** */

/*
 * @Author: TYTY000 <767280080@qq.com>
 * @Date: 2023-05-24 19:09:03
 * @Last Modified by: TYTY000 <767280080@qq.com>
 * @Last Modified time: 2023-05-25 18:23:32
 */

#ifndef __HASHTABLE__
#define __HASHTABLE__

#include "../SkipList/Dictionary.h"
#include "../SkipList/Entry.h"
#include "../vector/vector.h"
#include <cstring>
#include <fstream>
#include <iostream>
#include <string>

using namespace std;
using Rank = unsigned int;

template <typename K, typename V> class HashTable : public Dictionary<K, V> {
  friend class Print;

private:
  Entry<K, V> **dic;
  Rank M, N;
  Vector<int> v;

protected:
  void rehash();
  Rank probe4Free(const K &k); // find a bucket to fill.
  Rank probe4Hit(const K &k);  // find a bucket matched.
public:
  HashTable(Rank c = 5);
  ~HashTable();
  Rank size() const { return N; }
  bool put(K k, V v);
  V *get(K k);
  bool remove(K k);
};
static Rank hashCode(char c) { return (Rank)c; }
static Rank hashCode(int k) { return (Rank)k; }
static Rank hashCode(long long i) { return (Rank)((i >> 32) + (int)i); }
static Rank hashCode(char s[]) {
  Rank n = strlen(s);
  Rank h = 0;
  for (Rank i = 0; i < n; i++) {
    h = (h << 5) | (h >> 27);
    h += s[i];
  }
  return h;
}

#include "hashtable.h"
#endif // !__HASHTABLE__
